package 剑指offer_leetcode;

/**
 * JZ83剪绳子_进阶版
 */
public class 剑指Offer14_II_剪绳子_II {
    long mod = 1000000007;
    public int cuttingRope(int n) {
        if(n<=3)
            return n-1;
        long res = n / 3;
        int Mod = n % 3;
        if(Mod==0)
            return (int)(pow(3,res)%mod);
        else if(Mod==1)
            return (int)((pow(3,res-1) * 4)%mod);
        else
            return (int) ((pow(3,res) * 2)%mod);
    }
    //快速幂
    // 13 = 2^3 + 2^2 + 2^0 ==== 1 1 0 1
    long pow(long a , long n){
        long res = 1;
        while(n!=0){
            if(n%2==1)
                res=(res * a)%mod;
            a=(a*a)%mod;
            n /= 2;
        }
        return res%mod;
    }
}
